package 数据结构专栏.B_链表专栏.training;

import 数据结构专栏.B_链表专栏.ListNode;
import 数据结构专栏.B_链表专栏.ListUtil;

public class Test3_20240313 {
    public static void main(String[] args) {
//        ListNode list = ListUtil.getList();
//        System.out.println();
//        ListUtil.printList(delDuplicate(list));
        // 构建一个示例链表
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
//        head.next.next = new ListNode(2);
//        head.next.next.next = new ListNode(1);

        boolean isPalindrome = isPalindrome(head);
        System.out.println("是否为回文链表: " + isPalindrome);
    }

    // 1. 删除重复项(0)
    public static ListNode delDuplicate(ListNode head) {
        if (head == null || head.next == null) return head;
        head.next = delDuplicate(head.next);
        if (head.val == head.next.val) {
            head.next = head.next.next;
        }

        return head;
    }

    // 2. 反转单链表(1) 使用递归写法 o(n) o(n)
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode cur = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }


    // 3. 删除链表指定节点
    public static void delListNode(ListNode node) {

        if (node == null || node.next == null) return;
        node.next = node.next.next;
        node.val = node.next.val;

    }

    // 删除链表中节点值为val的节点
    public ListNode deleteNode(ListNode head, int val) {
        if (head.val == val) return head.next;
        ListNode pre = head, cur = head.next;
        while (cur != null && cur.val != val) {
            pre = cur;
            cur = cur.next;
        }
        if (cur != null) {
            pre.next = cur.next;
        }

        return head;
    }


    // 4. 判断链表是否有环 (0) 快慢指针解法
    public static boolean hasLoop2(ListNode n) {
        ListNode fast = n, slow = n;

        while (slow != null && fast != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow.val == fast.val) {
                return true;
            }
        }

        return false;
    }


    // 5.合并两个已排序链表
    public static ListNode mergeList(ListNode l1, ListNode l2) {

        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeList(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeList(l2.next, l1);
            return l2;
        }
    }


    // 6. 求链表倒数第K节点 (0)
    public static ListNode getKNode(ListNode head, int k) {


        return null;
    }


    // 7. 链表局部反转 （92. 反转链表 II ，难度为 中等)
    // 单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
    // 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
    public ListNode reverseBetween(ListNode head, int l, int r) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        r -= l;
        ListNode hh = dummy;
        while (l-- > 1) hh = hh.next;

        ListNode a = hh.next, b = a.next;
        while (r-- > 0) {
            ListNode tmp = b.next;
            b.next = a;
            a = b;
            b = tmp;
        }

        hh.next.next = b;
        hh.next = a;
        return dummy.next;
    }

    // 8. 回文链表检测：判断一个链表是否为回文链表。
    // 用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题
    public static boolean isPalindrome(ListNode head) {
        // 前指针和后指针
        ListNode left = head;
        ListNode right = head;

        while (right.next != null) {
            // 后指针向右移动
            right = right.next;
        }

        // 反转后半部分链表
        while (right != left) {
            ListNode temp = right.next;
            right.next = left;
            left = left.next;
            right.next = temp;
        }

        // 判断前后半部分是否相等
        while (left != null && right != null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }

        return true;
    }

}
